package B.链表;

import java.util.HashMap;
import java.util.Map;

public class _234_回文链表 {
    /**
     * 自解：使用快慢指针遍历 前半部分放map里
     * --浪费空间
     * 优化--先快慢指针 得到中间点 然后使用反转链表
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode low = head;
        ListNode high = head;
        Map<Integer, ListNode> map = new HashMap<>();
        int count = 0;

        //存一半到map中
        while (high != null && high.next != null) {
            map.put(count, low);
            count++;
            low = low.next;
            high = high.next.next;
        }
        //原为奇数 跳过中间数
        if (high == null){
            low = low;

        }else if (high.next == null) {
            low = low.next;
        }

        for (int i = count - 1; i >= 0; i--) {
            if (map.get(i).val == low.val) {
                low = low.next;
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 递归方法：从第一个和最后一个开始对比 因为第一个节点需要定义与后移 所以不能本函数本省直接递归
     * 因此在本方法中写定义保存 调用另一个递归函数
     * @param head
     * @return
     */

    ListNode temp;
    public boolean isPalindrome1(ListNode head) {
        temp =head;
        return judge(head);
    }

    //1-这个函数用来判断head和cur数值是不是相等的
    public boolean judge(ListNode cur){
        //2-递归终止条件==如果cur为空 表示本身传入空 回文
        if(cur ==null){
            return true;
        }

        //递归等价关系式，本题特殊点 不是数值运算操作所以没有真正意义上的等价 另外因为还要进行判断操作 所以不能；立刻返回操作

        if (!judge(cur.next)){//一个过程返回false 整个就返回 但一个true不一定都是true 所以也不能直接递归返回
            return false;
        }

        //上一个if是上一节点返回 下面是本节点计算
        if (temp.val != cur.val){
            return  false;
        }
        temp = temp.next;

        return true;
    }

}
